/*
题目描述：求斐波那契数列
方法：
1. 递归
2. 循环 O(n)
3. 数学公式转化成矩阵乘法 O(logn)

//拓展
青蛙跳台阶问题
一只青蛙一次可以跳上一级台阶，也可以跳上两级台阶，求该青蛙跳上一个n级台阶总共有多少种跳发？
f(n) = f(n - 1) + f(n -2)
 */
public class E10 {
    public static void main(String[] args){
        int n = 8;
        long res1 = Fibonacci1(n);
        long res2 = Fibonacci2(n);
        long res3 = Fibonacci3(n);

        System.out.println("res1 = " + res1);
        System.out.println("res2 = " + res2);
        System.out.println("res3 = " + res3);
    }
    //递归
    private static long Fibonacci1(int n){
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        return Fibonacci1(n - 1) + Fibonacci1(n - 2);
    }
    //循环
    private static long Fibonacci2(int n){
        int[] result = {0,1};
        if(n < 2){
            return result[n];
        }

        long f1 = 1;
        long f2 = 0;
        long res = 0;
        for(int i = 2; i <= n; i++){
            res = f1 + f2;
            f2 = f1;
            f1 = res;
        }
        return res;
    }
    //矩阵相乘
    private static long Fibonacci3(int n){
        int[] result = {0,1};
        if(n < 2){
            return result[n];
        }
        Matrix2By2 res = MatrixPower(n - 1);
        return res.m00;

    }

    static class Matrix2By2{
        private int m00;
        private int m01;
        private int m10;
        private int m11;

        public Matrix2By2(int m00, int m01, int m10, int m11){
            this.m00 = m00;
            this.m01 = m01;
            this.m10 = m10;
            this.m11 = m11;
        }
    }

    private static Matrix2By2 MatrixMutiply(final Matrix2By2 matrix1, final Matrix2By2 matrix2){
        return new Matrix2By2(
                matrix1.m00 * matrix2.m00 + matrix1.m01 * matrix2.m10,
                matrix1.m00 * matrix2.m01 + matrix1.m01 * matrix2.m11,
                matrix1.m10 * matrix2.m00 + matrix1.m11 * matrix2.m10,
                matrix1.m10 * matrix2.m01 + matrix1.m11 * matrix2.m11
        );
    }

    private static Matrix2By2 MatrixPower(int n){
        if(n <= 0){
            return null;
        }
        Matrix2By2 matrix = null;
        if(1 == n){
            matrix = new Matrix2By2(1,1,1,0);
        }
        else if(n % 2 == 0){
            matrix = MatrixPower(n/2);
            matrix = MatrixMutiply(matrix, matrix);
        }
        else if(n % 2 == 1){
            matrix = MatrixPower((n - 1)/2);
            matrix = MatrixMutiply(matrix, matrix);
            matrix = MatrixMutiply(matrix, new Matrix2By2(1,1,1,0));
        }
        return matrix;
    }
}
/*
res1 = 21
res2 = 21
res3 = 21
 */